//  AdaptiveGrid.java
//
//  Author:
//       Antonio J. Nebro <antonio@lcc.uma.es>
//       Juan J. Durillo <durillo@lcc.uma.es>
//
//  Copyright (c) 2011 Antonio J. Nebro, Juan J. Durillo
//
//  This program is free software: you can redistribute it and/or modify
//  it under the terms of the GNU Lesser General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU Lesser General Public License for more details.
// 
//  You should have received a copy of the GNU Lesser General Public License
//  along with this program.  If not, see <http://www.gnu.org/licenses/>.

package etmo.util;

import etmo.core.Solution;
import etmo.core.SolutionSet;

/**
 * This class defines an adaptive grid over a SolutionSet as the one used the
 * algorithm PAES.
 */
public class AdaptiveGrid {

	/**
	 * Number of bi-divisions of the objective space
	 */
	private int bisections_;

	/**
	 * Objectives of the problem
	 */
	private int objectives_;

	/**
	 * Number of solutions into a specific hypercube in the adaptative grid
	 */
	private int[] hypercubes_;

	/**
	 * 
	 * Grid lower bounds
	 */
	private double[] lowerLimits_;

	/**
	 * Grid upper bounds
	 */
	private double[] upperLimits_;

	/**
	 * Size of hypercube for each dimension
	 */
	private double[] divisionSize_;

	/**
	 * Hypercube with maximum number of solutions
	 */
	private int mostPopulated_;

	/**
	 * Hndicates when an hypercube has solutions
	 */
	private int[] occupied_;

	/**
	 * Constructor. Creates an instance of AdaptativeGrid.
	 * 
	 * @param bisections
	 *            Number of bi-divisions of the objective space.
	 * @param objetives
	 *            Number of objectives of the problem.
	 */
	public AdaptiveGrid(int bisections, int objetives) {
		bisections_ = bisections;
		objectives_ = objetives;
		lowerLimits_ = new double[objectives_];
		upperLimits_ = new double[objectives_];
		divisionSize_ = new double[objectives_];
		hypercubes_ = new int[(int) Math.pow(2.0, bisections_ * objectives_)];

		for (int i = 0; i < hypercubes_.length; i++)
			hypercubes_[i] = 0;
	} // AdaptativeGrid

	/**
	 * Updates the grid limits considering the solutions contained in a
	 * <code>SolutionSet</code>.
	 * 
	 * @param solutionSet
	 *            The <code>SolutionSet</code> considered.
	 */
	private void updateLimits(SolutionSet solutionSet) {
		// Init the lower and upper limits
		for (int obj = 0; obj < objectives_; obj++) {
			// Set the lower limits to the max real
			lowerLimits_[obj] = Double.MAX_VALUE;
			// Set the upper limits to the min real
			upperLimits_[obj] = Double.MIN_VALUE;
		} // for

		// Find the max and min limits of objetives into the population
		for (int ind = 0; ind < solutionSet.size(); ind++) {
			Solution tmpIndividual = solutionSet.get(ind);
			for (int obj = 0; obj < objectives_; obj++) {
				if (tmpIndividual.getObjective(obj) < lowerLimits_[obj]) {
					lowerLimits_[obj] = tmpIndividual.getObjective(obj);
				}
				if (tmpIndividual.getObjective(obj) > upperLimits_[obj]) {
					upperLimits_[obj] = tmpIndividual.getObjective(obj);
				}
			} // for
		} // for
	} // updateLimits

	/**
	 * Updates the grid adding solutions contained in a specific
	 * <code>SolutionSet</code>. <b>REQUIRE</b> The grid limits must have been
	 * previously calculated.
	 * 
	 * @param solutionSet
	 *            The <code>SolutionSet</code> considered.
	 */
	private void addSolutionSet(SolutionSet solutionSet) {
		// Calculate the location of all individuals and update the grid
		mostPopulated_ = 0;
		int location;

		for (int ind = 0; ind < solutionSet.size(); ind++) {
			location = location(solutionSet.get(ind));
			hypercubes_[location]++;
			if (hypercubes_[location] > hypercubes_[mostPopulated_])
				mostPopulated_ = location;
		} // for

		// The grid has been updated, so also update ocuppied's hypercubes
		calculateOccupied();
	} // addSolutionSet

	/**
	 * Updates the grid limits and the grid content adding the solutions
	 * contained in a specific <code>SolutionSet</code>.
	 * 
	 * @param solutionSet
	 *            The <code>SolutionSet</code>.
	 */
	public void updateGrid(SolutionSet solutionSet) {
		// Update lower and upper limits
		updateLimits(solutionSet);

		// Calculate the division size
		for (int obj = 0; obj < objectives_; obj++) {
			divisionSize_[obj] = upperLimits_[obj] - lowerLimits_[obj];
		} // for

		// Clean the hypercubes
		for (int i = 0; i < hypercubes_.length; i++) {
			hypercubes_[i] = 0;
		}

		// Add the population
		addSolutionSet(solutionSet);
	} // updateGrid

	/**
	 * Updates the grid limits and the grid content adding a new
	 * <code>Solution</code>. If the solution falls out of the grid bounds, the
	 * limits and content of the grid must be re-calculated.
	 * 
	 * @param solution
	 *            <code>Solution</code> considered to update the grid.
	 * @param solutionSet
	 *            <code>SolutionSet</code> used to update the grid.
	 */
	public void updateGrid(Solution solution, SolutionSet solutionSet) {

		int location = location(solution);
		if (location == -1) {// Re-build the Adaptative-Grid
			// Update lower and upper limits
			updateLimits(solutionSet);

			// Actualize the lower and upper limits whit the individual
			for (int obj = 0; obj < objectives_; obj++) {
				if (solution.getObjective(obj) < lowerLimits_[obj])
					lowerLimits_[obj] = solution.getObjective(obj);
				if (solution.getObjective(obj) > upperLimits_[obj])
					upperLimits_[obj] = solution.getObjective(obj);
			} // for

			// Calculate the division size
			for (int obj = 0; obj < objectives_; obj++) {
				divisionSize_[obj] = upperLimits_[obj] - lowerLimits_[obj];
			}

			// Clean the hypercube
			for (int i = 0; i < hypercubes_.length; i++) {
				hypercubes_[i] = 0;
			}

			// add the population
			addSolutionSet(solutionSet);
		} // if
	} // updateGrid

	/**
	 * Calculates the hypercube of a solution.
	 * 
	 * @param solution
	 *            The <code>Solution</code>.
	 */
	public int location(Solution solution) {
		// Create a int [] to store the range of each objetive
		int[] position = new int[objectives_];

		// Calculate the position for each objetive
		for (int obj = 0; obj < objectives_; obj++) {

			if ((solution.getObjective(obj) > upperLimits_[obj]) || (solution.getObjective(obj) < lowerLimits_[obj]))
				return -1;
			else if (solution.getObjective(obj) == lowerLimits_[obj])
				position[obj] = 0;
			else if (solution.getObjective(obj) == upperLimits_[obj])
				position[obj] = ((int) Math.pow(2.0, bisections_)) - 1;
			else {
				double tmpSize = divisionSize_[obj];
				double value = solution.getObjective(obj);
				double account = lowerLimits_[obj];
				int ranges = (int) Math.pow(2.0, bisections_);
				for (int b = 0; b < bisections_; b++) {
					tmpSize /= 2.0;
					ranges /= 2;
					if (value > (account + tmpSize)) {
						position[obj] += ranges;
						account += tmpSize;
					} // if
				} // for
			} // if
		}

		// Calcualate the location into the hypercubes
		int location = 0;
		for (int obj = 0; obj < objectives_; obj++) {
			location += position[obj] * Math.pow(2.0, obj * bisections_);
		}
		return location;
	} // location

	/**
	 * Returns the value of the most populated hypercube.
	 * 
	 * @return The hypercube with the maximum number of solutions.
	 */
	public int getMostPopulated() {
		return mostPopulated_;
	} // getMostPopulated

	/**
	 * Returns the number of solutions into a specific hypercube.
	 * 
	 * @param location
	 *            Number of the hypercube.
	 * @return The number of solutions into a specific hypercube.
	 */
	public int getLocationDensity(int location) {
		return hypercubes_[location];
	} // getLocationDensity

	/**
	 * Decreases the number of solutions into a specific hypercube.
	 * 
	 * @param location
	 *            Number of hypercube.
	 */
	public void removeSolution(int location) {
		// Decrease the solutions in the location specified.
		hypercubes_[location]--;

		// Update the most poblated hypercube
		if (location == mostPopulated_)
			for (int i = 0; i < hypercubes_.length; i++)
				if (hypercubes_[i] > hypercubes_[mostPopulated_])
					mostPopulated_ = i;

		// If hypercubes[location] now becomes to zero, then update ocupped
		// hypercubes
		if (hypercubes_[location] == 0)
			this.calculateOccupied();
	} // removeSolution

	/**
	 * Increases the number of solutions into a specific hypercube.
	 * 
	 * @param location
	 *            Number of hypercube.
	 */
	public void addSolution(int location) {
		// Increase the solutions in the location specified.
		hypercubes_[location]++;

		// Update the most poblated hypercube
		if (hypercubes_[location] > hypercubes_[mostPopulated_])
			mostPopulated_ = location;

		// if hypercubes[location] becomes to one, then recalculate
		// the occupied hypercubes
		if (hypercubes_[location] == 1)
			this.calculateOccupied();
	} // addSolution

	/**
	 * Returns the number of bi-divisions performed in each objective.
	 * 
	 * @return the number of bi-divisions.
	 */
	public int getBisections() {
		return bisections_;
	} // getBisections

	/**
	 * Retunrns a String representing the grid.
	 * 
	 * @return The String.
	 */
	public String toString() {
		String result = "Grid\n";
		for (int obj = 0; obj < objectives_; obj++) {
			result += "Objective " + obj + " " + lowerLimits_[obj] + " " + upperLimits_[obj] + "\n";
		} // for
		return result;
	} // toString

	/**
	 * Returns a random hypercube using a rouleteWheel method.
	 * 
	 * @return the number of the selected hypercube.
	 */
	public int rouletteWheel() {
		// Calculate the inverse sum
		double inverseSum = 0.0;
		for (int aHypercubes_ : hypercubes_) {
			if (aHypercubes_ > 0) {
				inverseSum += 1.0 / (double) aHypercubes_;
			}
		}

		// Calculate a random value between 0 and sumaInversa
		double random = PseudoRandom.randDouble(0.0, inverseSum);
		int hypercube = 0;
		double accumulatedSum = 0.0;
		while (hypercube < hypercubes_.length) {
			if (hypercubes_[hypercube] > 0) {
				accumulatedSum += 1.0 / (double) hypercubes_[hypercube];
			} // if

			if (accumulatedSum > random) {
				return hypercube;
			} // if

			hypercube++;
		} // while

		return hypercube;
	} // rouletteWheel

	/**
	 * Calculates the number of hypercubes having one or more solutions. return
	 * the number of hypercubes with more than zero solutions.
	 */
	public int calculateOccupied() {
		int total = 0;
		for (int aHypercubes_ : hypercubes_) {
			if (aHypercubes_ > 0) {
				total++;
			} // if
		} // for

		occupied_ = new int[total];
		int base = 0;
		for (int i = 0; i < hypercubes_.length; i++) {
			if (hypercubes_[i] > 0) {
				occupied_[base] = i;
				base++;
			} // if
		} // for

		return total;
	} // calculateOcuppied

	/**
	 * Returns the number of hypercubes with more than zero solutions.
	 * 
	 * @return the number of hypercubes with more than zero solutions.
	 */
	public int occupiedHypercubes() {
		return occupied_.length;
	} // occupiedHypercubes

	/**
	 * Returns a random hypercube that has more than zero solutions.
	 * 
	 * @return The hypercube.
	 */
	public int randomOccupiedHypercube() {
		int rand = PseudoRandom.randInt(0, occupied_.length - 1);
		return occupied_[rand];
	} // randomOccupiedHypercube
} // AdaptativeGrid
